class Solution
{
public:
    int maximumPoints(vector<vector<int>> &edges, vector<int> &coins, int k)
    {
        int n = coins.size();
        vector<vector<int>> graph(n);
        for (auto &edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        vector<vector<int>> cache(n, vector<int>(15, -1));
        function<int(int, int, int)> dfs = [&](int node, int parent, int decreaseTimes)
        {
            if (decreaseTimes >= 14)
            {
                return 0;
            }
            if (cache[node][decreaseTimes] != -1)
            {
                return cache[node][decreaseTimes];
            }
            int result1 = (coins[node] >> decreaseTimes) - k;
            int result2 = coins[node] >> (decreaseTimes + 1);
            for (auto neighbor : graph[node])
            {
                if (neighbor != parent)
                {
                    result1 += dfs(neighbor, node, decreaseTimes);
                    result2 += dfs(neighbor, node, decreaseTimes + 1);
                }
            }
            return cache[node][decreaseTimes] = max(result1, result2);
        };

        return dfs(0, -1, 0);
    }
};